/* http://en.wikipedia.org/wiki/Longest_increasing_subsequence */
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

/* dynamic programming, O(N^2). */
string longest_increasing_subsequence(const string &s) {
    if (s.length() <= 1) {
        return s;
    }
    int i, j, *longest;
    string res;
    longest = new int[s.length()];
    /* fill */
    for (i = 0; i < s.length(); i++) {
        longest[i] = 1;
        for (j = 0; j < i; j++) {
            if (s[j] < s[i]) {
                if (longest[i] < longest[j] + 1) {
                    longest[i] = longest[j] + 1;
                }
            }
        }
    }
#if 0 /* output */
    for (i = 0; i < s.length(); i++) {
        cout << longest[i] << " " << endl;
    }
#endif
    int currlen, minvalue, minpvalue = 255;
    i = s.length()-1;
    while (i >= 0) {
        currlen = longest[i];
        minvalue = s[i];
        while (longest[i] == currlen) {
            if (minvalue > s[i] && s[i] < minpvalue) {
                minvalue = s[i];
            }
            i--;
        }
        res.push_back(minvalue);
        minpvalue = minvalue;
    }
    /* free */
    delete[] longest;
    std::reverse(res.begin(), res.end());
    return res;
}

int bisearch(const string &s, int len, char c) {
    int left = 0, right = len-1;
    int mid;
    while (left <= right) {
        mid = left + (right-left)/2;
        if (s[mid] == c) {
            return mid;
        } else if (s[mid] > c) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left; // XXX
}

/* dynamic programming, O(NlogN). */
string longest_increasing_subsequence2(const string &s) {
    if (s.length() <= 1) {
        return s;
    }
    int i, j;
    string longestchars(s.length(), 0);
    j = 0;
    longestchars[j++] = s[0];
    /* fill */
    for (i = 1; i < s.length(); i++) {
        if (longestchars[j-1] < s[i] ) {
            longestchars[j++] = s[i];
        } else {
            int pos = bisearch(longestchars, j, s[i]); /* find the position to insert */
            longestchars[pos] = s[i];
        }
    }
    return longestchars;
}

int main() {
    string s = "127365";
    string r = longest_increasing_subsequence(s);
    cout << r << endl;
    return 0;
}
